package com;

import lombok.Data;

import javax.sound.midi.Soundbank;
import java.security.interfaces.ECKey;
import java.util.Collection;
import java.util.Map;
import java.util.Set;

/**
 * @author 罗俊华
 * @date 2021/5/13 - 10:23 上午
 */
public class BinarySearchTree<Key extends Comparable<Key>, Val> implements Map<Key, Val> {

    public Node<Key, Val> parent;

    public int size = 0;

    @Data
    public static class Node<Key, Val> {
        Key key;
        Val val;
        Node<Key, Val> left;
        Node<Key, Val> right;
        int N;

        public Node(Key key, Val val, Node<Key, Val> left, Node<Key, Val> right, int n) {
            this.key = key;
            this.val = val;
            this.left = left;
            this.right = right;
            N = n;
        }
    }

    public int size() {
        return 0;
    }

    public boolean isEmpty() {
        return size == 0;
    }

    public boolean containsKey(Object key) {
        return false;
    }

    public boolean containsValue(Object value) {
        return false;
    }

    public Val get(Object keyObj) {

        if (!(keyObj instanceof Comparable)) {
            return null;
        }

        Comparable<Key> key = (Comparable) keyObj;

        int compareResult = 0;

        Node<Key, Val> next = this.parent;

        while (next != null) {

            compareResult = key.compareTo(next.key);

            if (compareResult > 0) {
                next = next.right;
                continue;
            }
            if (compareResult < 0) {
                next = next.left;
                continue;
            }
            return next.val;
        }

        return null;
    }

    public Val put(Key key, Val value) {

        if (this.size == 0) {
            this.parent = new Node<Key, Val>(key, value, null, null, 1);
            size++;
            return value;
        }

        Node<Key, Val> next = this.parent;

        int compareResult = 0;

        while (true) {

            compareResult = key.compareTo(next.key);

            if (compareResult > 0) {
                if (next.right == null) {
//                    没有找到该节点
                    break;
                }
                next.N++;
                next = next.right;
            } else if (compareResult < 0) {
                if (next.left == null) {
                    break;
                }
                next.N++;
                next = next.left;
            } else {
//                命中
                Val oldValue = next.val;
//                next.key = key;
                next.val = value;
                return oldValue;
            }
        }

        if (compareResult > 0) {

            next.right = new Node<Key, Val>(key, value, null, null, 1);
        } else {
//            compareResult < 0
            next.left = new Node<Key, Val>(key, value, null, null, 1);
        }
        next.N += 1;
        size++;
        return value;
    }

    public Node<Key, Val> getMinNode() {
        Node<Key, Val> next = this.parent;
        return getMinNode(next);
    }

    private Node<Key, Val> getMinNode(Node<Key, Val> next) {
        if (next == null) {
            return null;
        }
        while (true) {
            if (next.left == null) {
                return next;
            }
            next = next.left;
        }
    }


    public Node<Key, Val> getMaxNode() {
        Node<Key, Val> next = this.parent;

        if (next == null) {
            return null;
        }

        while (true) {
            if (next.right == null) {
                return next;
            }
            next = next.right;
        }

    }

    public Node<Key, Val> floor(Key key) {
        if (this.parent == null) {
            return null;
        }
        return recursionFloor(this.parent, key);
    }

    public Node<Key, Val> recursionFloor(Node<Key, Val> node, Key key) {

        if (node == null) {
            return null;
        }
        int compareResult = key.compareTo(node.key);
        Node<Key, Val> childNode = null;
        if (compareResult > 0) {
//            往右边查找有没有比当前节点更大，但是又符合不能超过key的节点
            childNode = recursionFloor(node.right, key);

        } else if (compareResult < 0) {
//            小于等于key的的最大键 floor(key) 一定在节点的左子树中

            childNode = recursionFloor(node.left, key);

        } else {
//            compareResult <= 0 ，在left的树，所有节点都没有当前的大，就不用继续往下找了
            return node;
        }

//      如果往 right 或者 left 找到的节点仍然比要找的key小，那么可以直接返回childNode，因为找到的节点不符合条件，已经比key大了
        if (childNode != null && key.compareTo(childNode.key) >= 0) {
            return childNode;
        }
        return node;
    }

    public int rank(Key key) {
        int compareResult = key.compareTo(this.parent.key);
        int leftN = this.parent.left == null ? 0 : this.parent.left.N;

        if (compareResult < 0) {

            return this.rank(this.parent.left, key);
        } else if (compareResult > 0) {
            return leftN + 1 + this.rank(this.parent.right, key);
        } else {
            return leftN + 1;
        }
    }

    private int rank(Node<Key, Val> node, Key key) {

        if (node == null) {
            return 0;
        }

        int compareResult = key.compareTo(node.key);

        if (compareResult < 0) {
            return rank(node.left, key);
        } else if (compareResult > 0) {
            return rank(node.right, key);
        } else {
            return node.N;
        }

    }

    public Key select(int k) {
        if (this.parent == null) {
            return null;
        }
        int compareResult = k - this.parent.N;
        if (compareResult < 0) {
            return this.select(this.parent.left, k);

        } else if (compareResult > 0) {
            return this.select(this.parent.right, k);
        }
        return this.parent.key;
    }

    private Key select(Node<Key, Val> node, int k) {

        int compareResult = k - node.N;

        if (compareResult < 0) {
            if (node.left != null) {

                return this.select(node.left, k);
            }

        } else if (compareResult > 0) {
            if (node.right != null) {

                return this.select(node.right, k);
            }
        }
        return node.key;
    }


    public Node<Key, Val> deleteMin() {

        return this.deleteMin(this.parent);
    }

    /**
     * 如果最小节点就是根节点，那么就无法删除了
     *
     * @param node
     * @return 此方法返回的结果只是为了递归能成立，调用者得到的结果并没有任何意义
     */
    private Node<Key, Val> deleteMin(Node<Key, Val> node) {
        /**
         * 删除最小节点时，如果被删除节点的右边还有尾随的节点，那么删除节点之后，
         * 还要把被删除节点的右子树给接到被删除节点的父节点上，
         * 注意：删除最小节点时，该节点的左子树一定为 null，如果左子树不为 null，那么左子树中就必定含有比当前节点更小的节点
         */
        if (node.left == null) {
            size--;
            /**
             * 找到被删除节点的右节点
             */
            return node.right;
        }
        /**
         * 递归查找最小节点（被删除节点）的右子树，如果当前节点不是被删除的节点，那么最终
         * deleteMin(node.left) 返回的还是 return node.left，不会进行任何的变更
         * */
        node.left = this.deleteMin(node.left);

        node.N--;
        /**
         * 这里可以保证，如果此节点不是要删除的节点，那么将原封不动的返回递归时传进来的参数
         * 保证         node.left = this.deleteMin(node.left); 不会有任何变化
         */
        return node;

    }

    /*
    不用递归很难实现
    public Node<Key, Val> deleteMin() {
        if (this.parent == null) {
            return null;
        }
        Node<Key, Val> next = this.parent;
        while (true) {
            Node<Key, Val> leftChild = next.left;
            if (leftChild != null ) {
                if(leftChild.left == null){
                    next.left = leftChild.right;
                    size--;
                    return leftChild;
                }

            }
            if (leftChild == null && next.right == null) {

            }
        }

    }*/

    public void show() {

        if (this.parent == null) {
            return;
        }

        this.show(this.parent);
    }

    private void show(Node<Key, Val> node) {
        if (node == null) {
            return;
        }

        if (node.left != null) {
            this.show(node.left);
        }
        System.out.printf("%s，", node.key);

        if (node.right != null) {
            this.show(node.right);
        }
    }

    public Val remove(Object keyObj) {
        if (!(keyObj instanceof Comparable)) {
            return null;
        }

        Comparable<Key> key = (Comparable<Key>) keyObj;

        if (key == this.parent.key) {

        }

        int compareResult = 0;

        Node<Key, Val> next = this.parent;

        //      即将被删除的节点的父节点
        Node<Key, Val> parentOfDeletedNode = next;

        while (true) {

            compareResult = key.compareTo(next.key);
            if (compareResult > 0) {
                if (next.right != null) {
                    parentOfDeletedNode = next;

                    next = next.right;
                    continue;
                }
                return null;
            }
            if (compareResult < 0) {
                if (next.left != null) {
                    parentOfDeletedNode = next;

                    next = next.left;
                    continue;
                }
                return null;
            }
//            找到目标节点了，next就是将要被删除的节点
            break;
        }
//      即将被删除的节点
        Node<Key, Val> nodeForDeleting = next;

        if (nodeForDeleting == null) {
            return null;
        }

        /**
         * 从被删除节点的右子树中找到最小的节点，这个节点将顶替被删除的节点，
         * 因为右子树中的所有节点都比被删除节点大，而右子树中最小的节点，
         * 既大于被删除节点的左子树的所有节点，又小于被删除节点右子树的所有节点（除了它自己）
         * 是唯一一个能顶替被删除节点的节点
         */
        Node<Key, Val> newNodeForReplaceDeletedNode = getMinNode(next.right);
        if (newNodeForReplaceDeletedNode != null) {
            if (newNodeForReplaceDeletedNode == nodeForDeleting.right) {

            } else {
                newNodeForReplaceDeletedNode.right = nodeForDeleting.right;
            }
            newNodeForReplaceDeletedNode.left = nodeForDeleting.left;
        }


        if (parentOfDeletedNode.left == nodeForDeleting) {
            parentOfDeletedNode.left = newNodeForReplaceDeletedNode;
        } else {
            parentOfDeletedNode.right = newNodeForReplaceDeletedNode;
        }
        if (newNodeForReplaceDeletedNode != null) {
            deleteMin(newNodeForReplaceDeletedNode);
        }
        return null;
    }


    public void putAll(Map<? extends Key, ? extends Val> m) {

    }

    public void clear() {

    }

    public Set<Key> keySet() {
        return null;
    }

    public Collection<Val> values() {
        return null;
    }

    public Set<Entry<Key, Val>> entrySet() {
        return null;
    }
}
